package com.peng.leetcode.dynamic;

/**
 * DynamicMain
 * 动态规划
 *
 * @author: lupeng6
 * @create: 2020/12/29 15:44
 */
public class DynamicMain {

    public static void main(String[] args) {
        int[] goods = {2, 2, 4, 6, 3};
        int capacity = 9;
//        System.out.println(new DynamicMain().maxWeight(goods, capacity));
//        System.out.println(new Solution1().maxWeightPruning(goods, capacity));
//        System.out.println(new Solution2().dynamic(goods, capacity));
//        System.out.println(new Solution2().dynamic(goods, capacity));
        System.out.println(new Solution4().dynamic(goods, capacity));
    }

    /**
     * 回溯法, 将所有的可能枚举, 计算最大重量
     *
     * @author lupeng6
     * @date 2020/12/29 16:08
     */
    static class Solution {
        private Integer maxWeight = Integer.MIN_VALUE;

        public int maxWeight(int[] goods, int capacity) {
            dfs(goods, capacity, 0, 0);
            return maxWeight;
        }

        private void dfs(int[] goods, int capacity, int index, int currentWeight) {
            if (currentWeight == capacity || index == goods.length) {
                maxWeight = Math.max(currentWeight, maxWeight);
                return;
            }
            // 将第 index 个物品装入背包
            if (currentWeight + goods[index] <= capacity) {
                dfs(goods, capacity, index + 1, currentWeight + goods[index]);
            }

            // 不装第 index 个物品
            dfs(goods, capacity, index + 1, currentWeight);
        }
    }

    /**
     * 回溯 + 剪枝
     *
     * @author lupeng6
     * @date 2020/12/29 16:10
     */
    static class Solution1 {
        private Integer maxWeight = Integer.MIN_VALUE;

        public int maxWeightPruning(int[] goods, int capacity) {
            this.marked = new boolean[goods.length][capacity + 1];
            dfsPruning(goods, capacity, 0, 0);
            return maxWeight;
        }

        private boolean[][] marked;

        private void dfsPruning(int[] goods, int capacity, int index, int currentWeight) {
            if (currentWeight == capacity || index == goods.length) {
                maxWeight = Math.max(currentWeight, maxWeight);
                return;
            }
            if (marked[index][currentWeight]) {
                return;
            }
            marked[index][currentWeight] = true;
            // 将第 index 个物品装入背包
            if (currentWeight + goods[index] <= capacity) {
                dfsPruning(goods, capacity, index + 1, currentWeight + goods[index]);
            }

            // 不装第 index 个物品
            dfsPruning(goods, capacity, index + 1, currentWeight);
        }
    }

    /**
     * 动态规划
     *
     * dp[x] = Math.max(dp[x - goods[0]] + 1, dp[x - goods[1]] + 1)
     *
     * @author lupeng6
     * @date 2020/12/29 16:22
     */
    static class Solution2 {

        public int dynamic(int[] goods, int capacity) {
            boolean[][] states = new boolean[goods.length][capacity + 1];
            states[0][0] = true;
            if (goods[0] <= capacity) {
                states[0][goods[0]] = true;
            }
            for (int i = 1; i < goods.length; i++) {
                // 第i个物品不放入背包
                for (int j = 0; j < capacity; j++) {
                    if (states[i - 1][j] == true) {
                        states[i][j] = states[i - 1][j];
                    }
                }

                // 第i个物品放入背包
                for (int j = 0; j <= capacity - goods[i]; j++) {
                    if (states[i - 1][j] == true) {
                        states[i][goods[i] + j] = true;
                    }
                }
            }

            for (int i = capacity; i >= 0; i--) {
                if (states[goods.length - 1][i] == true) {
                    return i;
                }
            }
            return 0;
        }
    }

    /**
     * 动态规划2, 使用以为素组记录动态转移过程
     *
     * @author lupeng6
     * @date 2020/12/29 17:34
     */
    static class Solution3 {
        public int dynamic(int[] goods, int capacity) {
            int length = goods.length;
            boolean[] states = new boolean[capacity + 1];
            states[0] = true;
            if (goods[0] <= capacity) {
                states[goods[0]] = true;
            }
            for (int i = 1; i < goods.length; i++) {
                int goodsWeight = goods[i];
                for (int j = 0; j <= capacity - goodsWeight; j++) {
                    if (states[j] == true) {
                        states[j + goodsWeight] = true;
                    }
                }
            }
            for (int i = states.length - 1; i >= 0; i--) {
                if (states[i]) {
                    return i;
                }
            }
            return 0;
        }
    }

    /**
     * 递归的方式, 实现 动态规划
     *
     * @author lupeng6
     * @date 2020/12/29 21:22
     */
    static class Solution4 {
        private boolean[][] marked;

        private int[] goods;

        private int capacity;

        public int dynamic(int[] goods, int capacity) {
            this.goods = goods;
            this.capacity = capacity;
            this.marked = new boolean[goods.length][capacity + 1];
            return recursion(0, 0);
        }

        public int recursion(int index, int curWeight) {
            if (index == goods.length || curWeight == capacity) {
                return curWeight;
            }
            if (marked[index][curWeight]) {
                return curWeight;
            }
            marked[index][curWeight] = true;
            int notIn = recursion(index + 1, curWeight);

            int in = Integer.MIN_VALUE;
            if (goods[index] <= capacity - curWeight) {
                in = recursion(index + 1, curWeight + goods[index]);
            }
            return Math.max(notIn, in);
        }
    }
 }
